﻿#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<stack>
#include<algorithm>
#include<bitset>
#include<cstring>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
using ll = long long;

/*
	题目描述：
	有n 枚石子。两位玩家定了如下规则进行游戏：
	· Mirko 先取一次，Slavko 再取一次，然后 Mirko 再取一次，两人轮流取石子，以此类推;
	· Mirko 在第一次取石子时可以取走任意多个;
	· 接下来，每次至少要取走一个石子，最多取走上一次取的数量的 2 倍。当然，玩家取走的数量必须不大于目前场上剩余的石子数量。
	· 取走最后一块石子的玩家获胜
	双方都以最优策略取石子。Mirko 想知道，自己第一次至少要取走几颗石子最终才能够获胜。
	【输入格式】
	输入一行一个整数 n 表示石子的数量。
	【输出格式】
	输出一行一个整数，表示 Mirko 最少取多少石子可以保证获胜。
*/

// 题目分析：
// 
//     a b c
// 1 1 2 3 5 8 13 21 34 .....
// 任何一个斐波那契数，如果第一次不全拿，那就是必败态 (a * 2 > b && a * 2 < c)
// 换言之，面对一个斐波那契数，如果当前角色不能一次性取完，即败
// 
// Zeckendorf 定理: 
// 任何一个正整数都可以拆分成两个不相邻的斐波那契数
// 1 = 1 (本身就是斐波那契数)
// 2 = 2
// 3 = 3
// 4 = 1 + 3 
// 5 = 5 
// 6 = 1 + 5 
// 7 = 2 + 5 
// ....
// ....
//
//

const ll INF = 1e15 + 10;
ll n, cn;
ll f[105];
ll Find(ll n)
{
	int l = 0, r = cn;
	while (l < r)
	{
		int mid = l + r + 1>> 1;
		if (f[mid] <= n) l = mid;
		else r = mid - 1;
	}
	return f[l];
}
int main()
{
	// 预处理斐波那契数列
	f[0] = 1, f[1] = 2;
	cn = 1;
	while (f[cn] <= INF)
	{
		f[cn + 1] = f[cn] + f[cn - 1];
		++cn;
	}

	cin >> n;
	ll ret = -1, cur;
	while (n != 1 && n != 2)
	{
		cur = Find(n);
		if (n == cur)
		{
			ret = cur;
			break;
		}
		else n -= cur;
	}
	if (ret != -1) cout << ret << "\n";
	else cout << n << "\n";
	return 0;
}